package 热题100.双指针.接雨水_42;
/*
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

思想：
      以每一个下标为例，考虑：
        Q1：首先什么情况下下标i能接上雨水？
        A1：统计下标i开始往左最高的柱子maxleft和往右最高的柱子maxright，取二者的较小值 - 下标i本身高度。
      朴素做法：
        1. 从左至右统计每个位置i左边最高的柱子，即leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        2. 从右至左统计每个位置i右边最高的柱子，即rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        3. 然后遍历整个i取左右最高柱子的较小值 - 柱子i本身的高度
      双指针做法：
        将维护数组，转换为维护左右两个柱子。
        1. 首指针在左边第一个位置，尾指针指向在最右边的位置。
        2. 首指针从左至右，首先leftMax[i]是根据左指针遍历的每个柱子i来更新，如果左指针指到的柱子高度 >= 尾指针柱子高度，说明
        leftMax[i] >= rightMax[i]，这是因为如果遍历到一个较大的height[i]，如果另一边没有比它大，那么另一边就会一直往这边靠，
        不会出现 height[left]<height[right]，leftMax>rightMax的情况，因为 height[left] 必定 >= leftMax
 * */
public class Solution {
    public static void main(String[] args) {
        int[] height = {4, 2, 0, 3, 2, 5};
        System.out.println(trap(height));
    }
    public static int trap(int[] height) {
        int ans = 0;
        if (height.length == 0){
            return ans;
        }
        int left = 0, right = height.length - 1;
        while (left < right){

            if (height[left] < height[right]){
                // 先更新
            }
        }
        //
        return ans;
    }
}

